package com.leetcode.partition2;

/**
 * @author `RKC`
 * @date 2021/8/12 22:36
 */
public class LC169多数元素 {

    public static int majorityElement(int[] nums) {
        return divide(nums, 0, nums.length - 1);
    }

    public static void main(String[] args) {
//        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        int[] nums = {2, 3, 3};
        System.out.println(majorityElement(nums));
    }

    //分治法
    private static int divide(int[] nums, int left, int right) {
        //当分为一个元素为一组时，该组的多数元素就是自己
        if (left == right) return nums[left];
        int mid = left + (right - left) / 2;
        //得到左和右的多数元素
        int leftNum = divide(nums, left, mid);
        int rightNum = divide(nums, mid + 1, right);
        if (leftNum == rightNum) return leftNum;        //左右的多数元素相同，直接返回
        //左右的多数元素不一样，则对左右的多数元素进行计数，多者为多数元素
        int leftCount = 0, rightCount = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] == leftNum) leftCount++;
            else if (nums[i] == rightNum) rightCount++;
        }
        return leftCount > rightCount ? leftNum : rightNum;
    }
}
